package com.stefan.tree;

import java.util.NoSuchElementException;

//二叉查找树/二叉排序树
//这个类本生就是Tree里面的一个TreeNode，但是他是root TreeNode
//依然所有Integer的地方都应该是E
public class BinarySearchTree<E>{
    Integer data;
    BinarySearchTree<E> left;
    BinarySearchTree<E> right;
    BinarySearchTree<E> parent;
    public BinarySearchTree(Integer data) {
        this.data = data;
    }

    public void insert (Integer data,BinarySearchTree<Integer> root) {
//        if (root == null)
        if (data > root.data) { //放右边
            if (root.right == null) {
                root.right = new BinarySearchTree(data);
                root.right.parent = root;
            } else {
                insert(data,root.right);
            }
        } else {
            //放左边
            if (root.left == null) {
                root.left = new BinarySearchTree(data);
                root.left.parent = root;
            } else {
                insert(data,root.left);
            }
        }
    }

    //查找的过程其实就是insert的过程。
    public BinarySearchTree<Integer> find (Integer data,BinarySearchTree<Integer> root) {
        BinarySearchTree<Integer> result = null;
        if (root != null) {
            if (data > root.data) { //找的时候和insert时候唯一的区别就是，这个条件满足后，右子树就不可能为null
                //不然树就不会被build起来
                result = find(data,root.right);
            } else if (data < root.data){
                //左子树也一样
                result= find(data,root.left);
            } else {
                //相等的话就找到啦
                System.out.println("找到了： " + root);
                System.out.println(data);
                result =  root;
            }
        }
        return result;
    }

    /*
    * 二叉搜索树的删除：
    * 1.删除的节点是叶子节点 -> 直接删除
    * 2.删除的节点只有一个子树（左或右）-> @1子树的根节点代替该节点， @2存在孩子节点就用孩子节点替换子树的根节点
    * 3.删除的节点有2个子树（左和右）,找后继节点（第一个比该节点大的节点），
    * 而且后继节点的左子树一定为null（为什么？如果存在左子树，那么左子树一定比当前的后继节点小，
    * 那找到的后继节点就不是后继节点，后继节点的概念：第一个比删除元素大的）
    * 总结一下上面说的，后继节点必然左子树是null，右子树是null的话后继节点就是叶子节点
    * 此时就是2的情况，这里就是递归。
    * */
    public void delete (Integer data,BinarySearchTree<Integer> root) {
        BinarySearchTree<Integer> treeNode = find(data, root);
        if (treeNode == null) {
            throw new NoSuchElementException();
        }

        if (treeNode.left == null && treeNode.right == null) {//是叶子节点就直接删除 -  左右子树都null
            if (treeNode.data > treeNode.parent.data) {
                //节点在右边
                treeNode.parent.right = null;
            } else {
                //节点在左边
                treeNode.parent.left = null;
            }
        } else if (treeNode.left != null && treeNode.right != null) {//删除的节点有2个子树（左和右）,找后继节点
            BinarySearchTree<Integer> extend = findExtend(treeNode); //找到后继节点

        } else {//节点只有一棵子树，左或者右子
            //左子树
            if (treeNode.left != null) {
                if (treeNode.data > treeNode.parent.data) {
                    //节点在右边
                    treeNode.parent.right = treeNode.left;
                } else {
                    //节点在左边
                    treeNode.parent.left = treeNode.left;
                }
                treeNode.left.parent = treeNode.parent;
            }
            //右子树
            if (treeNode.right != null) {
                if (treeNode.data > treeNode.parent.data) {
                    //节点在右边
                    treeNode.parent.right = treeNode.right;
                } else {
                    //节点在左边
                    treeNode.parent.left = treeNode.right;
                }
                treeNode.right.parent = treeNode.parent;
            }
        }

    }

    //找后继节点
    public BinarySearchTree<Integer> findExtend(BinarySearchTree<Integer> node) {
        // 1.后继需要在右子树里面找，
        BinarySearchTree<Integer> right = node.right;
        if (right == null) {
            return node;
        }
        //2.在右子树里面找到最小的 - 那就是找右子树里面的左子树，这里是个递归
        return findMin(right);
    }
    public BinarySearchTree<Integer> findMin(BinarySearchTree<Integer> node) {
        BinarySearchTree<Integer> left = node.left;
        if (left == null) { //不存在左子树，则当前node就是最小的
            return node;
        }
        return findMin(left);
    }

    //中序排列验证二叉搜索树的正确性
    public void mid(BinarySearchTree<Integer> root) {
        BinarySearchTree<Integer> left = root.left;
        if (left != null) {
            mid(left); //左子树作为一个树继续
        }
        System.out.print(root.data); //根节点输出

        BinarySearchTree<Integer> right = root.right;
        if (right != null) {
            mid(right);//又子树作为一个树继续
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bs = new BinarySearchTree<>(8); //根节点
        bs.insert(9,bs);
        bs.insert(10,bs);
        bs.insert(5,bs);
        bs.insert(7,bs);
        bs.insert(4,bs);
        bs.insert(2,bs);
        bs.mid(bs);
        System.out.println("");
        BinarySearchTree<Integer> find = bs.find(7, bs);
        System.out.println(find);
    }
}
